package com.gxc.recursion;

/**
 * 背包问题
 * 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表i号物品的重量和价值。
 * 给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。
 * 返回你能装下最多的价值是多少?
 */
public class Backpack {

    public static void main(String[] args) {
        int[] weights = {3,2,4,7};
        int[] values = {5,6,3,19};
        int bag = 11;

        System.out.println(maxValue(weights, values, bag));
    }

    /**
     *
     * @param weights  物品的重量
     * @param values   物品的价值
     * @param bag      背包大小
     * @return
     */
    public static int maxValue(int[] weights, int[] values, int bag) {
        return process(weights, values, 0, bag);
    }

    /**
     *
     * @param weights 物品的重量
     * @param values  物品的价值
     * @param i       当前第几个物品
     * @param bag     背包大小
     * @return
     */
    private static int process(int[] weights, int[] values, int i, int bag) {
        //如果背包已经超过
        if (bag<=0) return 0;
        //如果物品已经选择完了
        if (i == weights.length) return 0;

        int selectValue = 0;
        //不要物品
        int noValue = process(weights, values, i+1, bag);
        //要物品的前提是背包空间大于物品的重量
        if (bag > weights[i]) selectValue = values[i] + process(weights, values, i+1, bag-weights[i]);
        return Math.max(selectValue, noValue);
    }

}
